package leetcode_800;

/**
 *@author 周杨
 *SmallestRotationWithHighestScore_798 一个数组的任意元素 如果小于等于其index 则数组加分1 问在何处旋转数组 能获得最大积分
 *describe:感觉是数学问题 没有太看懂逻辑 AC 36%
 *see:https://www.cnblogs.com/grandyang/p/9272921.html
 *2018年10月24日 上午10:47:15
 */
public class SmallestRotationWithHighestScore_798 {
	public int bestRotation(int[] A) {
        int []dp=new int[A.length];
        for(int i=0;i<A.length;++i) {
        	dp[(i-A[i]+1+A.length)%A.length]--;
        }
        int max=0;
        for(int i=1;i<A.length;++i) {
        	dp[i]+=dp[i-1]+1;
        	max=dp[i]>dp[max]?i:max;
        }
        return max-dp[0];
        	
    }
}
